/*
 * Copyright 2010-2021 JetBrains s.r.o. and Kotlin Programming Language contributors.
 * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file.
 */

package kotlin.text.regex

private val decompositionValues = intArrayOf(
    65, 768, 65, 769, 65, 770, 65, 771, 65, 776, 65, 778, 67, 807, 69, 768,
    69, 769, 69, 770, 69, 776, 73, 768, 73, 769, 73, 770, 73, 776, 78, 771,
    79, 768, 79, 769, 79, 770, 79, 771, 79, 776, 85, 768, 85, 769, 85, 770,
    85, 776, 89, 769, 97, 768, 97, 769, 97, 770, 97, 771, 97, 776, 97, 778,
    99, 807, 101, 768, 101, 769, 101, 770, 101, 776, 105, 768, 105, 769, 105, 770,
    105, 776, 110, 771, 111, 768, 111, 769, 111, 770, 111, 771, 111, 776, 117, 768,
    117, 769, 117, 770, 117, 776, 121, 769, 121, 776, 65, 772, 97, 772, 65, 774,
    97, 774, 65, 808, 97, 808, 67, 769, 99, 769, 67, 770, 99, 770, 67, 775,
    99, 775, 67, 780, 99, 780, 68, 780, 100, 780, 69, 772, 101, 772, 69, 774,
    101, 774, 69, 775, 101, 775, 69, 808, 101, 808, 69, 780, 101, 780, 71, 770,
    103, 770, 71, 774, 103, 774, 71, 775, 103, 775, 71, 807, 103, 807, 72, 770,
    104, 770, 73, 771, 105, 771, 73, 772, 105, 772, 73, 774, 105, 774, 73, 808,
    105, 808, 73, 775, 74, 770, 106, 770, 75, 807, 107, 807, 76, 769, 108, 769,
    76, 807, 108, 807, 76, 780, 108, 780, 78, 769, 110, 769, 78, 807, 110, 807,
    78, 780, 110, 780, 79, 772, 111, 772, 79, 774, 111, 774, 79, 779, 111, 779,
    82, 769, 114, 769, 82, 807, 114, 807, 82, 780, 114, 780, 83, 769, 115, 769,
    83, 770, 115, 770, 83, 807, 115, 807, 83, 780, 115, 780, 84, 807, 116, 807,
    84, 780, 116, 780, 85, 771, 117, 771, 85, 772, 117, 772, 85, 774, 117, 774,
    85, 778, 117, 778, 85, 779, 117, 779, 85, 808, 117, 808, 87, 770, 119, 770,
    89, 770, 121, 770, 89, 776, 90, 769, 122, 769, 90, 775, 122, 775, 90, 780,
    122, 780, 79, 795, 111, 795, 85, 795, 117, 795, 65, 780, 97, 780, 73, 780,
    105, 780, 79, 780, 111, 780, 85, 780, 117, 780, 85, 776, 772, 117, 776, 772,
    85, 776, 769, 117, 776, 769, 85, 776, 780, 117, 776, 780, 85, 776, 768, 117,
    776, 768, 65, 776, 772, 97, 776, 772, 65, 775, 772, 97, 775, 772, 198, 772,
    230, 772, 71, 780, 103, 780, 75, 780, 107, 780, 79, 808, 111, 808, 79, 808,
    772, 111, 808, 772, 439, 780, 658, 780, 106, 780, 71, 769, 103, 769, 78, 768,
    110, 768, 65, 778, 769, 97, 778, 769, 198, 769, 230, 769, 216, 769, 248, 769,
    65, 783, 97, 783, 65, 785, 97, 785, 69, 783, 101, 783, 69, 785, 101, 785,
    73, 783, 105, 783, 73, 785, 105, 785, 79, 783, 111, 783, 79, 785, 111, 785,
    82, 783, 114, 783, 82, 785, 114, 785, 85, 783, 117, 783, 85, 785, 117, 785,
    83, 806, 115, 806, 84, 806, 116, 806, 72, 780, 104, 780, 65, 775, 97, 775,
    69, 807, 101, 807, 79, 776, 772, 111, 776, 772, 79, 771, 772, 111, 771, 772,
    79, 775, 111, 775, 79, 775, 772, 111, 775, 772, 89, 772, 121, 772, 768, 769,
    787, 776, 769, 697, 59, 168, 769, 913, 769, 183, 917, 769, 919, 769, 921, 769,
    927, 769, 933, 769, 937, 769, 953, 776, 769, 921, 776, 933, 776, 945, 769, 949,
    769, 951, 769, 953, 769, 965, 776, 769, 953, 776, 965, 776, 959, 769, 965, 769,
    969, 769, 978, 769, 978, 776, 1045, 768, 1045, 776, 1043, 769, 1030, 776, 1050, 769,
    1048, 768, 1059, 774, 1048, 774, 1080, 774, 1077, 768, 1077, 776, 1075, 769, 1110, 776,
    1082, 769, 1080, 768, 1091, 774, 1140, 783, 1141, 783, 1046, 774, 1078, 774, 1040, 774,
    1072, 774, 1040, 776, 1072, 776, 1045, 774, 1077, 774, 1240, 776, 1241, 776, 1046, 776,
    1078, 776, 1047, 776, 1079, 776, 1048, 772, 1080, 772, 1048, 776, 1080, 776, 1054, 776,
    1086, 776, 1256, 776, 1257, 776, 1069, 776, 1101, 776, 1059, 772, 1091, 772, 1059, 776,
    1091, 776, 1059, 779, 1091, 779, 1063, 776, 1095, 776, 1067, 776, 1099, 776, 1575, 1619,
    1575, 1620, 1608, 1620, 1575, 1621, 1610, 1620, 1749, 1620, 1729, 1620, 1746, 1620, 2344, 2364,
    2352, 2364, 2355, 2364, 2325, 2364, 2326, 2364, 2327, 2364, 2332, 2364, 2337, 2364, 2338, 2364,
    2347, 2364, 2351, 2364, 2503, 2494, 2503, 2519, 2465, 2492, 2466, 2492, 2479, 2492, 2610, 2620,
    2616, 2620, 2582, 2620, 2583, 2620, 2588, 2620, 2603, 2620, 2887, 2902, 2887, 2878, 2887, 2903,
    2849, 2876, 2850, 2876, 2962, 3031, 3014, 3006, 3015, 3006, 3014, 3031, 3142, 3158, 3263, 3285,
    3270, 3285, 3270, 3286, 3270, 3266, 3270, 3266, 3285, 3398, 3390, 3399, 3390, 3398, 3415, 3545,
    3530, 3545, 3535, 3545, 3535, 3530, 3545, 3551, 3906, 4023, 3916, 4023, 3921, 4023, 3926, 4023,
    3931, 4023, 3904, 4021, 3953, 3954, 3953, 3956, 4018, 3968, 4019, 3968, 3953, 3968, 3986, 4023,
    3996, 4023, 4001, 4023, 4006, 4023, 4011, 4023, 3984, 4021, 4133, 4142, 65, 805, 97, 805,
    66, 775, 98, 775, 66, 803, 98, 803, 66, 817, 98, 817, 67, 807, 769, 99,
    807, 769, 68, 775, 100, 775, 68, 803, 100, 803, 68, 817, 100, 817, 68, 807,
    100, 807, 68, 813, 100, 813, 69, 772, 768, 101, 772, 768, 69, 772, 769, 101,
    772, 769, 69, 813, 101, 813, 69, 816, 101, 816, 69, 807, 774, 101, 807, 774,
    70, 775, 102, 775, 71, 772, 103, 772, 72, 775, 104, 775, 72, 803, 104, 803,
    72, 776, 104, 776, 72, 807, 104, 807, 72, 814, 104, 814, 73, 816, 105, 816,
    73, 776, 769, 105, 776, 769, 75, 769, 107, 769, 75, 803, 107, 803, 75, 817,
    107, 817, 76, 803, 108, 803, 76, 803, 772, 108, 803, 772, 76, 817, 108, 817,
    76, 813, 108, 813, 77, 769, 109, 769, 77, 775, 109, 775, 77, 803, 109, 803,
    78, 775, 110, 775, 78, 803, 110, 803, 78, 817, 110, 817, 78, 813, 110, 813,
    79, 771, 769, 111, 771, 769, 79, 771, 776, 111, 771, 776, 79, 772, 768, 111,
    772, 768, 79, 772, 769, 111, 772, 769, 80, 769, 112, 769, 80, 775, 112, 775,
    82, 775, 114, 775, 82, 803, 114, 803, 82, 803, 772, 114, 803, 772, 82, 817,
    114, 817, 83, 775, 115, 775, 83, 803, 115, 803, 83, 769, 775, 115, 769, 775,
    83, 780, 775, 115, 780, 775, 83, 803, 775, 115, 803, 775, 84, 775, 116, 775,
    84, 803, 116, 803, 84, 817, 116, 817, 84, 813, 116, 813, 85, 804, 117, 804,
    85, 816, 117, 816, 85, 813, 117, 813, 85, 771, 769, 117, 771, 769, 85, 772,
    776, 117, 772, 776, 86, 771, 118, 771, 86, 803, 118, 803, 87, 768, 119, 768,
    87, 769, 119, 769, 87, 776, 119, 776, 87, 775, 119, 775, 87, 803, 119, 803,
    88, 775, 120, 775, 88, 776, 120, 776, 89, 775, 121, 775, 90, 770, 122, 770,
    90, 803, 122, 803, 90, 817, 122, 817, 104, 817, 116, 776, 119, 778, 121, 778,
    383, 775, 65, 803, 97, 803, 65, 777, 97, 777, 65, 770, 769, 97, 770, 769,
    65, 770, 768, 97, 770, 768, 65, 770, 777, 97, 770, 777, 65, 770, 771, 97,
    770, 771, 65, 803, 770, 97, 803, 770, 65, 774, 769, 97, 774, 769, 65, 774,
    768, 97, 774, 768, 65, 774, 777, 97, 774, 777, 65, 774, 771, 97, 774, 771,
    65, 803, 774, 97, 803, 774, 69, 803, 101, 803, 69, 777, 101, 777, 69, 771,
    101, 771, 69, 770, 769, 101, 770, 769, 69, 770, 768, 101, 770, 768, 69, 770,
    777, 101, 770, 777, 69, 770, 771, 101, 770, 771, 69, 803, 770, 101, 803, 770,
    73, 777, 105, 777, 73, 803, 105, 803, 79, 803, 111, 803, 79, 777, 111, 777,
    79, 770, 769, 111, 770, 769, 79, 770, 768, 111, 770, 768, 79, 770, 777, 111,
    770, 777, 79, 770, 771, 111, 770, 771, 79, 803, 770, 111, 803, 770, 79, 795,
    769, 111, 795, 769, 79, 795, 768, 111, 795, 768, 79, 795, 777, 111, 795, 777,
    79, 795, 771, 111, 795, 771, 79, 795, 803, 111, 795, 803, 85, 803, 117, 803,
    85, 777, 117, 777, 85, 795, 769, 117, 795, 769, 85, 795, 768, 117, 795, 768,
    85, 795, 777, 117, 795, 777, 85, 795, 771, 117, 795, 771, 85, 795, 803, 117,
    795, 803, 89, 768, 121, 768, 89, 803, 121, 803, 89, 777, 121, 777, 89, 771,
    121, 771, 945, 787, 945, 788, 945, 787, 768, 945, 788, 768, 945, 787, 769, 945,
    788, 769, 945, 787, 834, 945, 788, 834, 913, 787, 913, 788, 913, 787, 768, 913,
    788, 768, 913, 787, 769, 913, 788, 769, 913, 787, 834, 913, 788, 834, 949, 787,
    949, 788, 949, 787, 768, 949, 788, 768, 949, 787, 769, 949, 788, 769, 917, 787,
    917, 788, 917, 787, 768, 917, 788, 768, 917, 787, 769, 917, 788, 769, 951, 787,
    951, 788, 951, 787, 768, 951, 788, 768, 951, 787, 769, 951, 788, 769, 951, 787,
    834, 951, 788, 834, 919, 787, 919, 788, 919, 787, 768, 919, 788, 768, 919, 787,
    769, 919, 788, 769, 919, 787, 834, 919, 788, 834, 953, 787, 953, 788, 953, 787,
    768, 953, 788, 768, 953, 787, 769, 953, 788, 769, 953, 787, 834, 953, 788, 834,
    921, 787, 921, 788, 921, 787, 768, 921, 788, 768, 921, 787, 769, 921, 788, 769,
    921, 787, 834, 921, 788, 834, 959, 787, 959, 788, 959, 787, 768, 959, 788, 768,
    959, 787, 769, 959, 788, 769, 927, 787, 927, 788, 927, 787, 768, 927, 788, 768,
    927, 787, 769, 927, 788, 769, 965, 787, 965, 788, 965, 787, 768, 965, 788, 768,
    965, 787, 769, 965, 788, 769, 965, 787, 834, 965, 788, 834, 933, 788, 933, 788,
    768, 933, 788, 769, 933, 788, 834, 969, 787, 969, 788, 969, 787, 768, 969, 788,
    768, 969, 787, 769, 969, 788, 769, 969, 787, 834, 969, 788, 834, 937, 787, 937,
    788, 937, 787, 768, 937, 788, 768, 937, 787, 769, 937, 788, 769, 937, 787, 834,
    937, 788, 834, 945, 768, 945, 769, 949, 768, 949, 769, 951, 768, 951, 769, 953,
    768, 953, 769, 959, 768, 959, 769, 965, 768, 965, 769, 969, 768, 969, 769, 945,
    787, 837, 945, 788, 837, 945, 787, 768, 837, 945, 788, 768, 837, 945, 787, 769,
    837, 945, 788, 769, 837, 945, 787, 834, 837, 945, 788, 834, 837, 913, 787, 837,
    913, 788, 837, 913, 787, 768, 837, 913, 788, 768, 837, 913, 787, 769, 837, 913,
    788, 769, 837, 913, 787, 834, 837, 913, 788, 834, 837, 951, 787, 837, 951, 788,
    837, 951, 787, 768, 837, 951, 788, 768, 837, 951, 787, 769, 837, 951, 788, 769,
    837, 951, 787, 834, 837, 951, 788, 834, 837, 919, 787, 837, 919, 788, 837, 919,
    787, 768, 837, 919, 788, 768, 837, 919, 787, 769, 837, 919, 788, 769, 837, 919,
    787, 834, 837, 919, 788, 834, 837, 969, 787, 837, 969, 788, 837, 969, 787, 768,
    837, 969, 788, 768, 837, 969, 787, 769, 837, 969, 788, 769, 837, 969, 787, 834,
    837, 969, 788, 834, 837, 937, 787, 837, 937, 788, 837, 937, 787, 768, 837, 937,
    788, 768, 837, 937, 787, 769, 837, 937, 788, 769, 837, 937, 787, 834, 837, 937,
    788, 834, 837, 945, 774, 945, 772, 945, 768, 837, 945, 837, 945, 769, 837, 945,
    834, 945, 834, 837, 913, 774, 913, 772, 913, 768, 913, 769, 913, 837, 953, 168,
    834, 951, 768, 837, 951, 837, 951, 769, 837, 951, 834, 951, 834, 837, 917, 768,
    917, 769, 919, 768, 919, 769, 919, 837, 8127, 768, 8127, 769, 8127, 834, 953, 774,
    953, 772, 953, 776, 768, 953, 776, 769, 953, 834, 953, 776, 834, 921, 774, 921,
    772, 921, 768, 921, 769, 8190, 768, 8190, 769, 8190, 834, 965, 774, 965, 772, 965,
    776, 768, 965, 776, 769, 961, 787, 961, 788, 965, 834, 965, 776, 834, 933, 774,
    933, 772, 933, 768, 933, 769, 929, 788, 168, 768, 168, 769, 96, 969, 768, 837,
    969, 837, 969, 769, 837, 969, 834, 969, 834, 837, 927, 768, 927, 769, 937, 768,
    937, 769, 937, 837, 180, 8194, 8195, 937, 75, 65, 778, 8592, 824, 8594, 824, 8596,
    824, 8656, 824, 8660, 824, 8658, 824, 8707, 824, 8712, 824, 8715, 824, 8739, 824, 8741,
    824, 8764, 824, 8771, 824, 8773, 824, 8776, 824, 61, 824, 8801, 824, 8781, 824, 60,
    824, 62, 824, 8804, 824, 8805, 824, 8818, 824, 8819, 824, 8822, 824, 8823, 824, 8826,
    824, 8827, 824, 8834, 824, 8835, 824, 8838, 824, 8839, 824, 8866, 824, 8872, 824, 8873,
    824, 8875, 824, 8828, 824, 8829, 824, 8849, 824, 8850, 824, 8882, 824, 8883, 824, 8884,
    824, 8885, 824, 12296, 12297, 10973, 824, 12363, 12441, 12365, 12441, 12367, 12441, 12369, 12441, 12371,
    12441, 12373, 12441, 12375, 12441, 12377, 12441, 12379, 12441, 12381, 12441, 12383, 12441, 12385, 12441, 12388,
    12441, 12390, 12441, 12392, 12441, 12399, 12441, 12399, 12442, 12402, 12441, 12402, 12442, 12405, 12441, 12405,
    12442, 12408, 12441, 12408, 12442, 12411, 12441, 12411, 12442, 12358, 12441, 12445, 12441, 12459, 12441, 12461,
    12441, 12463, 12441, 12465, 12441, 12467, 12441, 12469, 12441, 12471, 12441, 12473, 12441, 12475, 12441, 12477,
    12441, 12479, 12441, 12481, 12441, 12484, 12441, 12486, 12441, 12488, 12441, 12495, 12441, 12495, 12442, 12498,
    12441, 12498, 12442, 12501, 12441, 12501, 12442, 12504, 12441, 12504, 12442, 12507, 12441, 12507, 12442, 12454,
    12441, 12527, 12441, 12528, 12441, 12529, 12441, 12530, 12441, 12541, 12441, 35912, 26356, 36554, 36040, 28369,
    20018, 21477, 40860, 40860, 22865, 37329, 21895, 22856, 25078, 30313, 32645, 34367, 34746, 35064, 37007, 27138,
    27931, 28889, 29662, 33853, 37226, 39409, 20098, 21365, 27396, 29211, 34349, 40478, 23888, 28651, 34253, 35172,
    25289, 33240, 34847, 24266, 26391, 28010, 29436, 37070, 20358, 20919, 21214, 25796, 27347, 29200, 30439, 32769,
    34310, 34396, 36335, 38706, 39791, 40442, 30860, 31103, 32160, 33737, 37636, 40575, 35542, 22751, 24324, 31840,
    32894, 29282, 30922, 36034, 38647, 22744, 23650, 27155, 28122, 28431, 32047, 32311, 38475, 21202, 32907, 20956,
    20940, 31260, 32190, 33777, 38517, 35712, 25295, 27138, 35582, 20025, 23527, 24594, 29575, 30064, 21271, 30971,
    20415, 24489, 19981, 27852, 25976, 32034, 21443, 22622, 30465, 33865, 35498, 27578, 36784, 27784, 25342, 33509,
    25504, 30053, 20142, 20841, 20937, 26753, 31975, 33391, 35538, 37327, 21237, 21570, 22899, 24300, 26053, 28670,
    31018, 38317, 39530, 40599, 40654, 21147, 26310, 27511, 36706, 24180, 24976, 25088, 25754, 28451, 29001, 29833,
    31178, 32244, 32879, 36646, 34030, 36899, 37706, 21015, 21155, 21693, 28872, 35010, 35498, 24265, 24565, 25467,
    27566, 31806, 29557, 20196, 22265, 23527, 23994, 24604, 29618, 29801, 32666, 32838, 37428, 38646, 38728, 38936,
    20363, 31150, 37300, 38584, 24801, 20102, 20698, 23534, 23615, 26009, 27138, 29134, 30274, 34044, 36988, 40845,
    26248, 38446, 21129, 26491, 26611, 27969, 28316, 29705, 30041, 30827, 32016, 39006, 20845, 25134, 38520, 20523,
    23833, 28138, 36650, 24459, 24900, 26647, 29575, 38534, 21033, 21519, 23653, 26131, 26446, 26792, 27877, 29702,
    30178, 32633, 35023, 35041, 37324, 38626, 21311, 28346, 21533, 29136, 29848, 34298, 38563, 40023, 40607, 26519,
    28107, 33256, 31435, 31520, 31890, 29376, 28825, 35672, 20160, 33590, 21050, 20999, 24230, 25299, 31958, 23429,
    27934, 26292, 36667, 34892, 38477, 35211, 24275, 20800, 21952, 22618, 26228, 20958, 29482, 30410, 31036, 31070,
    31077, 31119, 38742, 31934, 32701, 34322, 35576, 36920, 37117, 39151, 39164, 39208, 40372, 20398, 20711, 20813,
    21193, 21220, 21329, 21917, 22022, 22120, 22592, 22696, 23652, 23662, 24724, 24936, 24974, 25074, 25935, 26082,
    26257, 26757, 28023, 28186, 28450, 29038, 29227, 29730, 30865, 31038, 31049, 31048, 31056, 31062, 31069, 31117,
    31118, 31296, 31361, 31680, 32244, 32265, 32321, 32626, 32773, 33261, 33401, 33401, 33879, 35088, 35222, 35585,
    35641, 36051, 36104, 36790, 36920, 38627, 38911, 38971, 20006, 20917, 20840, 20352, 20805, 20864, 21191, 21242,
    21917, 21845, 21913, 21986, 22618, 22707, 22852, 22868, 23138, 23336, 24274, 24281, 24425, 24493, 24792, 24910,
    24840, 24974, 24928, 25074, 25140, 25540, 25628, 25682, 25942, 26228, 26391, 26395, 26454, 27513, 27578, 27969,
    28379, 28363, 28450, 28702, 29038, 30631, 29237, 29359, 29482, 29809, 29958, 30011, 30237, 30239, 30410, 30427,
    30452, 30538, 30528, 30924, 31409, 31680, 31867, 32091, 32244, 32574, 32773, 33618, 33775, 34681, 35137, 35206,
    35222, 35519, 35576, 35531, 35585, 35582, 35565, 35641, 35722, 36104, 36664, 36978, 37273, 37494, 38524, 38627,
    38742, 38875, 38911, 38923, 38971, 39698, 40860, 141386, 141380, 144341, 15261, 16408, 16441, 152137, 154832, 163539,
    40771, 40846, 1497, 1460, 1522, 1463, 1513, 1473, 1513, 1474, 1513, 1468, 1473, 1513, 1468, 1474,
    1488, 1463, 1488, 1464, 1488, 1468, 1489, 1468, 1490, 1468, 1491, 1468, 1492, 1468, 1493, 1468,
    1494, 1468, 1496, 1468, 1497, 1468, 1498, 1468, 1499, 1468, 1500, 1468, 1502, 1468, 1504, 1468,
    1505, 1468, 1507, 1468, 1508, 1468, 1510, 1468, 1511, 1468, 1512, 1468, 1513, 1468, 1514, 1468,
    1493, 1465, 1489, 1471, 1499, 1471, 1508, 1471, 119127, 119141, 119128, 119141, 119128, 119141, 119150, 119128,
    119141, 119151, 119128, 119141, 119152, 119128, 119141, 119153, 119128, 119141, 119154, 119225, 119141, 119226, 119141, 119225,
    119141, 119150, 119226, 119141, 119150, 119225, 119141, 119151, 119226, 119141, 119151, 20029, 20024, 20033, 131362, 20320,
    20398, 20411, 20482, 20602, 20633, 20711, 20687, 13470, 132666, 20813, 20820, 20836, 20855, 132380, 13497, 20839,
    20877, 132427, 20887, 20900, 20172, 20908, 20917, 168415, 20981, 20995, 13535, 21051, 21062, 21106, 21111, 13589,
    21191, 21193, 21220, 21242, 21253, 21254, 21271, 21321, 21329, 21338, 21363, 21373, 21375, 21375, 21375, 133676,
    28784, 21450, 21471, 133987, 21483, 21489, 21510, 21662, 21560, 21576, 21608, 21666, 21750, 21776, 21843, 21859,
    21892, 21892, 21913, 21931, 21939, 21954, 22294, 22022, 22295, 22097, 22132, 20999, 22766, 22478, 22516, 22541,
    22411, 22578, 22577, 22700, 136420, 22770, 22775, 22790, 22810, 22818, 22882, 136872, 136938, 23020, 23067, 23079,
    23000, 23142, 14062, 14076, 23304, 23358, 23358, 137672, 23491, 23512, 23527, 23539, 138008, 23551, 23558, 24403,
    23586, 14209, 23648, 23662, 23744, 23693, 138724, 23875, 138726, 23918, 23915, 23932, 24033, 24034, 14383, 24061,
    24104, 24125, 24169, 14434, 139651, 14460, 24240, 24243, 24246, 24266, 172946, 24318, 140081, 140081, 33281, 24354,
    24354, 14535, 144056, 156122, 24418, 24427, 14563, 24474, 24525, 24535, 24569, 24705, 14650, 14620, 24724, 141012,
    24775, 24904, 24908, 24910, 24908, 24954, 24974, 25010, 24996, 25007, 25054, 25074, 25078, 25104, 25115, 25181,
    25265, 25300, 25424, 142092, 25405, 25340, 25448, 25475, 25572, 142321, 25634, 25541, 25513, 14894, 25705, 25726,
    25757, 25719, 14956, 25935, 25964, 143370, 26083, 26360, 26185, 15129, 26257, 15112, 15076, 20882, 20885, 26368,
    26268, 32941, 17369, 26391, 26395, 26401, 26462, 26451, 144323, 15177, 26618, 26501, 26706, 26757, 144493, 26766,
    26655, 26900, 15261, 26946, 27043, 27114, 27304, 145059, 27355, 15384, 27425, 145575, 27476, 15438, 27506, 27551,
    27578, 27579, 146061, 138507, 146170, 27726, 146620, 27839, 27853, 27751, 27926, 27966, 28023, 27969, 28009, 28024,
    28037, 146718, 27956, 28207, 28270, 15667, 28363, 28359, 147153, 28153, 28526, 147294, 147342, 28614, 28729, 28702,
    28699, 15766, 28746, 28797, 28791, 28845, 132389, 28997, 148067, 29084, 148395, 29224, 29237, 29264, 149000, 29312,
    29333, 149301, 149524, 29562, 29579, 16044, 29605, 16056, 16056, 29767, 29788, 29809, 29829, 29898, 16155, 29988,
    150582, 30014, 150674, 30064, 139679, 30224, 151457, 151480, 151620, 16380, 16392, 30452, 151795, 151794, 151833, 151859,
    30494, 30495, 30495, 30538, 16441, 30603, 16454, 16534, 152605, 30798, 30860, 30924, 16611, 153126, 31062, 153242,
    153285, 31119, 31211, 16687, 31296, 31306, 31311, 153980, 154279, 154279, 31470, 16898, 154539, 31686, 31689, 16935,
    154752, 31954, 17056, 31976, 31971, 32000, 155526, 32099, 17153, 32199, 32258, 32325, 17204, 156200, 156231, 17241,
    156377, 32634, 156478, 32661, 32762, 32773, 156890, 156963, 32864, 157096, 32880, 144223, 17365, 32946, 33027, 17419,
    33086, 23221, 157607, 157621, 144275, 144284, 33281, 33284, 36766, 17515, 33425, 33419, 33437, 21171, 33457, 33459,
    33469, 33510, 158524, 33509, 33565, 33635, 33709, 33571, 33725, 33767, 33879, 33619, 33738, 33740, 33756, 158774,
    159083, 158933, 17707, 34033, 34035, 34070, 160714, 34148, 159532, 17757, 17761, 159665, 159954, 17771, 34384, 34396,
    34407, 34409, 34473, 34440, 34574, 34530, 34681, 34600, 34667, 34694, 17879, 34785, 34817, 17913, 34912, 34915,
    161383, 35031, 35038, 17973, 35066, 13499, 161966, 162150, 18110, 18119, 35488, 35565, 35722, 35925, 162984, 36011,
    36033, 36123, 36215, 163631, 133124, 36299, 36284, 36336, 133342, 36564, 36664, 165330, 165357, 37012, 37105, 37137,
    165678, 37147, 37432, 37591, 37592, 37500, 37881, 37909, 166906, 38283, 18837, 38327, 167287, 18918, 38595, 23986,
    38691, 168261, 168474, 19054, 19062, 38880, 168970, 19122, 169110, 38923, 38923, 38953, 169398, 39138, 19251, 39209,
    39335, 39362, 39422, 19406, 170800, 39698, 40000, 40189, 19662, 19693, 40295, 172238, 19704, 172293, 172558, 172689,
    40635, 19798, 40697, 40702, 40709, 40719, 40726, 40763, 173568,
)

private val decompositionValueIndex = shortArrayOf(
    0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30,
    32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62,
    64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94,
    96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126,
    128, 130, 132, 134, 136, 138, 140, 142, 144, 146, 148, 150, 152, 154, 156, 158,
    160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184, 186, 188, 190,
    192, 194, 196, 198, 200, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222,
    224, 226, 228, 230, 232, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254,
    256, 258, 260, 262, 264, 266, 268, 270, 272, 274, 276, 278, 280, 282, 284, 286,
    288, 290, 292, 294, 296, 298, 300, 302, 304, 306, 308, 310, 312, 314, 316, 318,
    320, 322, 324, 326, 328, 330, 332, 334, 336, 338, 340, 342, 344, 346, 349, 352,
    355, 358, 361, 364, 367, 370, 373, 376, 379, 382, 384, 386, 388, 390, 392, 394,
    396, 398, 401, 404, 406, 408, 410, 412, 414, 416, 418, 421, 424, 426, 428, 430,
    432, 434, 436, 438, 440, 442, 444, 446, 448, 450, 452, 454, 456, 458, 460, 462,
    464, 466, 468, 470, 472, 474, 476, 478, 480, 482, 484, 486, 488, 490, 492, 494,
    496, 498, 500, 503, 506, 509, 512, 514, 516, 519, 522, 524, 526, 527, 528, 529,
    531, 532, 533, 535, 537, 538, 540, 542, 544, 546, 548, 550, 553, 555, 557, 559,
    561, 563, 565, 568, 570, 572, 574, 576, 578, 580, 582, 584, 586, 588, 590, 592,
    594, 596, 598, 600, 602, 604, 606, 608, 610, 612, 614, 616, 618, 620, 622, 624,
    626, 628, 630, 632, 634, 636, 638, 640, 642, 644, 646, 648, 650, 652, 654, 656,
    658, 660, 662, 664, 666, 668, 670, 672, 674, 676, 678, 680, 682, 684, 686, 688,
    690, 692, 694, 696, 698, 700, 702, 704, 706, 708, 710, 712, 714, 716, 718, 720,
    722, 724, 726, 728, 730, 732, 734, 736, 738, 740, 742, 744, 746, 748, 750, 752,
    754, 756, 758, 760, 762, 764, 766, 768, 770, 772, 774, 777, 779, 781, 783, 785,
    787, 790, 792, 794, 796, 798, 800, 802, 804, 806, 808, 810, 812, 814, 816, 818,
    820, 822, 824, 826, 828, 830, 832, 834, 836, 838, 840, 842, 844, 847, 850, 852,
    854, 856, 858, 860, 862, 864, 866, 868, 870, 873, 876, 879, 882, 884, 886, 888,
    890, 893, 896, 898, 900, 902, 904, 906, 908, 910, 912, 914, 916, 918, 920, 922,
    924, 926, 928, 931, 934, 936, 938, 940, 942, 944, 946, 948, 950, 953, 956, 958,
    960, 962, 964, 966, 968, 970, 972, 974, 976, 978, 980, 982, 984, 986, 988, 990,
    992, 995, 998, 1001, 1004, 1007, 1010, 1013, 1016, 1018, 1020, 1022, 1024, 1026, 1028, 1030,
    1032, 1035, 1038, 1040, 1042, 1044, 1046, 1048, 1050, 1053, 1056, 1059, 1062, 1065, 1068, 1070,
    1072, 1074, 1076, 1078, 1080, 1082, 1084, 1086, 1088, 1090, 1092, 1094, 1096, 1099, 1102, 1105,
    1108, 1110, 1112, 1114, 1116, 1118, 1120, 1122, 1124, 1126, 1128, 1130, 1132, 1134, 1136, 1138,
    1140, 1142, 1144, 1146, 1148, 1150, 1152, 1154, 1156, 1158, 1160, 1162, 1164, 1166, 1168, 1170,
    1172, 1174, 1176, 1178, 1181, 1184, 1187, 1190, 1193, 1196, 1199, 1202, 1205, 1208, 1211, 1214,
    1217, 1220, 1223, 1226, 1229, 1232, 1235, 1238, 1240, 1242, 1244, 1246, 1248, 1250, 1253, 1256,
    1259, 1262, 1265, 1268, 1271, 1274, 1277, 1280, 1282, 1284, 1286, 1288, 1290, 1292, 1294, 1296,
    1299, 1302, 1305, 1308, 1311, 1314, 1317, 1320, 1323, 1326, 1329, 1332, 1335, 1338, 1341, 1344,
    1347, 1350, 1353, 1356, 1358, 1360, 1362, 1364, 1367, 1370, 1373, 1376, 1379, 1382, 1385, 1388,
    1391, 1394, 1396, 1398, 1400, 1402, 1404, 1406, 1408, 1410, 1412, 1414, 1417, 1420, 1423, 1426,
    1429, 1432, 1434, 1436, 1439, 1442, 1445, 1448, 1451, 1454, 1456, 1458, 1461, 1464, 1467, 1470,
    1472, 1474, 1477, 1480, 1483, 1486, 1488, 1490, 1493, 1496, 1499, 1502, 1505, 1508, 1510, 1512,
    1515, 1518, 1521, 1524, 1527, 1530, 1532, 1534, 1537, 1540, 1543, 1546, 1549, 1552, 1554, 1556,
    1559, 1562, 1565, 1568, 1571, 1574, 1576, 1578, 1581, 1584, 1587, 1590, 1592, 1594, 1597, 1600,
    1603, 1606, 1608, 1610, 1613, 1616, 1619, 1622, 1625, 1628, 1630, 1633, 1636, 1639, 1641, 1643,
    1646, 1649, 1652, 1655, 1658, 1661, 1663, 1665, 1668, 1671, 1674, 1677, 1680, 1683, 1685, 1687,
    1689, 1691, 1693, 1695, 1697, 1699, 1701, 1703, 1705, 1707, 1709, 1711, 1714, 1717, 1721, 1725,
    1729, 1733, 1737, 1741, 1744, 1747, 1751, 1755, 1759, 1763, 1767, 1771, 1774, 1777, 1781, 1785,
    1789, 1793, 1797, 1801, 1804, 1807, 1811, 1815, 1819, 1823, 1827, 1831, 1834, 1837, 1841, 1845,
    1849, 1853, 1857, 1861, 1864, 1867, 1871, 1875, 1879, 1883, 1887, 1891, 1893, 1895, 1898, 1900,
    1903, 1905, 1908, 1910, 1912, 1914, 1916, 1918, 1919, 1921, 1924, 1926, 1929, 1931, 1934, 1936,
    1938, 1940, 1942, 1944, 1946, 1948, 1950, 1952, 1954, 1957, 1960, 1962, 1965, 1967, 1969, 1971,
    1973, 1975, 1977, 1979, 1981, 1983, 1986, 1989, 1991, 1993, 1995, 1998, 2000, 2002, 2004, 2006,
    2008, 2010, 2012, 2013, 2016, 2018, 2021, 2023, 2026, 2028, 2030, 2032, 2034, 2036, 2037, 2038,
    2039, 2040, 2041, 2043, 2045, 2047, 2049, 2051, 2053, 2055, 2057, 2059, 2061, 2063, 2065, 2067,
    2069, 2071, 2073, 2075, 2077, 2079, 2081, 2083, 2085, 2087, 2089, 2091, 2093, 2095, 2097, 2099,
    2101, 2103, 2105, 2107, 2109, 2111, 2113, 2115, 2117, 2119, 2121, 2123, 2125, 2127, 2129, 2131,
    2132, 2133, 2135, 2137, 2139, 2141, 2143, 2145, 2147, 2149, 2151, 2153, 2155, 2157, 2159, 2161,
    2163, 2165, 2167, 2169, 2171, 2173, 2175, 2177, 2179, 2181, 2183, 2185, 2187, 2189, 2191, 2193,
    2195, 2197, 2199, 2201, 2203, 2205, 2207, 2209, 2211, 2213, 2215, 2217, 2219, 2221, 2223, 2225,
    2227, 2229, 2231, 2233, 2235, 2237, 2239, 2241, 2243, 2245, 2247, 2249, 2251, 2252, 2253, 2254,
    2255, 2256, 2257, 2258, 2259, 2260, 2261, 2262, 2263, 2264, 2265, 2266, 2267, 2268, 2269, 2270,
    2271, 2272, 2273, 2274, 2275, 2276, 2277, 2278, 2279, 2280, 2281, 2282, 2283, 2284, 2285, 2286,
    2287, 2288, 2289, 2290, 2291, 2292, 2293, 2294, 2295, 2296, 2297, 2298, 2299, 2300, 2301, 2302,
    2303, 2304, 2305, 2306, 2307, 2308, 2309, 2310, 2311, 2312, 2313, 2314, 2315, 2316, 2317, 2318,
    2319, 2320, 2321, 2322, 2323, 2324, 2325, 2326, 2327, 2328, 2329, 2330, 2331, 2332, 2333, 2334,
    2335, 2336, 2337, 2338, 2339, 2340, 2341, 2342, 2343, 2344, 2345, 2346, 2347, 2348, 2349, 2350,
    2351, 2352, 2353, 2354, 2355, 2356, 2357, 2358, 2359, 2360, 2361, 2362, 2363, 2364, 2365, 2366,
    2367, 2368, 2369, 2370, 2371, 2372, 2373, 2374, 2375, 2376, 2377, 2378, 2379, 2380, 2381, 2382,
    2383, 2384, 2385, 2386, 2387, 2388, 2389, 2390, 2391, 2392, 2393, 2394, 2395, 2396, 2397, 2398,
    2399, 2400, 2401, 2402, 2403, 2404, 2405, 2406, 2407, 2408, 2409, 2410, 2411, 2412, 2413, 2414,
    2415, 2416, 2417, 2418, 2419, 2420, 2421, 2422, 2423, 2424, 2425, 2426, 2427, 2428, 2429, 2430,
    2431, 2432, 2433, 2434, 2435, 2436, 2437, 2438, 2439, 2440, 2441, 2442, 2443, 2444, 2445, 2446,
    2447, 2448, 2449, 2450, 2451, 2452, 2453, 2454, 2455, 2456, 2457, 2458, 2459, 2460, 2461, 2462,
    2463, 2464, 2465, 2466, 2467, 2468, 2469, 2470, 2471, 2472, 2473, 2474, 2475, 2476, 2477, 2478,
    2479, 2480, 2481, 2482, 2483, 2484, 2485, 2486, 2487, 2488, 2489, 2490, 2491, 2492, 2493, 2494,
    2495, 2496, 2497, 2498, 2499, 2500, 2501, 2502, 2503, 2504, 2505, 2506, 2507, 2508, 2509, 2510,
    2511, 2512, 2513, 2514, 2515, 2516, 2517, 2518, 2519, 2520, 2521, 2522, 2523, 2524, 2525, 2526,
    2527, 2528, 2529, 2530, 2531, 2532, 2533, 2534, 2535, 2536, 2537, 2538, 2539, 2540, 2541, 2542,
    2543, 2544, 2545, 2546, 2547, 2548, 2549, 2550, 2551, 2552, 2553, 2554, 2555, 2556, 2557, 2558,
    2559, 2560, 2561, 2562, 2563, 2564, 2565, 2566, 2567, 2568, 2569, 2570, 2571, 2572, 2573, 2574,
    2575, 2576, 2577, 2578, 2579, 2580, 2581, 2582, 2583, 2584, 2585, 2586, 2587, 2588, 2589, 2590,
    2591, 2592, 2593, 2594, 2595, 2596, 2597, 2598, 2599, 2600, 2601, 2602, 2603, 2604, 2605, 2606,
    2607, 2608, 2609, 2610, 2611, 2612, 2613, 2614, 2615, 2616, 2617, 2618, 2619, 2620, 2621, 2622,
    2623, 2624, 2625, 2626, 2627, 2628, 2629, 2630, 2631, 2632, 2633, 2634, 2635, 2636, 2637, 2638,
    2639, 2640, 2641, 2642, 2643, 2644, 2645, 2646, 2647, 2648, 2649, 2650, 2651, 2652, 2653, 2654,
    2655, 2656, 2657, 2658, 2659, 2660, 2661, 2662, 2663, 2664, 2665, 2666, 2667, 2668, 2669, 2670,
    2671, 2672, 2673, 2674, 2675, 2676, 2677, 2678, 2679, 2680, 2681, 2682, 2683, 2684, 2685, 2686,
    2687, 2688, 2689, 2690, 2691, 2692, 2693, 2694, 2695, 2696, 2697, 2698, 2699, 2700, 2701, 2702,
    2703, 2704, 2705, 2706, 2708, 2710, 2712, 2714, 2717, 2720, 2722, 2724, 2726, 2728, 2730, 2732,
    2734, 2736, 2738, 2740, 2742, 2744, 2746, 2748, 2750, 2752, 2754, 2756, 2758, 2760, 2762, 2764,
    2766, 2768, 2770, 2772, 2774, 2776, 2778, 2780, 2783, 2786, 2789, 2792, 2795, 2797, 2799, 2802,
    2805, 2808, 2811, 2812, 2813, 2814, 2815, 2816, 2817, 2818, 2819, 2820, 2821, 2822, 2823, 2824,
    2825, 2826, 2827, 2828, 2829, 2830, 2831, 2832, 2833, 2834, 2835, 2836, 2837, 2838, 2839, 2840,
    2841, 2842, 2843, 2844, 2845, 2846, 2847, 2848, 2849, 2850, 2851, 2852, 2853, 2854, 2855, 2856,
    2857, 2858, 2859, 2860, 2861, 2862, 2863, 2864, 2865, 2866, 2867, 2868, 2869, 2870, 2871, 2872,
    2873, 2874, 2875, 2876, 2877, 2878, 2879, 2880, 2881, 2882, 2883, 2884, 2885, 2886, 2887, 2888,
    2889, 2890, 2891, 2892, 2893, 2894, 2895, 2896, 2897, 2898, 2899, 2900, 2901, 2902, 2903, 2904,
    2905, 2906, 2907, 2908, 2909, 2910, 2911, 2912, 2913, 2914, 2915, 2916, 2917, 2918, 2919, 2920,
    2921, 2922, 2923, 2924, 2925, 2926, 2927, 2928, 2929, 2930, 2931, 2932, 2933, 2934, 2935, 2936,
    2937, 2938, 2939, 2940, 2941, 2942, 2943, 2944, 2945, 2946, 2947, 2948, 2949, 2950, 2951, 2952,
    2953, 2954, 2955, 2956, 2957, 2958, 2959, 2960, 2961, 2962, 2963, 2964, 2965, 2966, 2967, 2968,
    2969, 2970, 2971, 2972, 2973, 2974, 2975, 2976, 2977, 2978, 2979, 2980, 2981, 2982, 2983, 2984,
    2985, 2986, 2987, 2988, 2989, 2990, 2991, 2992, 2993, 2994, 2995, 2996, 2997, 2998, 2999, 3000,
    3001, 3002, 3003, 3004, 3005, 3006, 3007, 3008, 3009, 3010, 3011, 3012, 3013, 3014, 3015, 3016,
    3017, 3018, 3019, 3020, 3021, 3022, 3023, 3024, 3025, 3026, 3027, 3028, 3029, 3030, 3031, 3032,
    3033, 3034, 3035, 3036, 3037, 3038, 3039, 3040, 3041, 3042, 3043, 3044, 3045, 3046, 3047, 3048,
    3049, 3050, 3051, 3052, 3053, 3054, 3055, 3056, 3057, 3058, 3059, 3060, 3061, 3062, 3063, 3064,
    3065, 3066, 3067, 3068, 3069, 3070, 3071, 3072, 3073, 3074, 3075, 3076, 3077, 3078, 3079, 3080,
    3081, 3082, 3083, 3084, 3085, 3086, 3087, 3088, 3089, 3090, 3091, 3092, 3093, 3094, 3095, 3096,
    3097, 3098, 3099, 3100, 3101, 3102, 3103, 3104, 3105, 3106, 3107, 3108, 3109, 3110, 3111, 3112,
    3113, 3114, 3115, 3116, 3117, 3118, 3119, 3120, 3121, 3122, 3123, 3124, 3125, 3126, 3127, 3128,
    3129, 3130, 3131, 3132, 3133, 3134, 3135, 3136, 3137, 3138, 3139, 3140, 3141, 3142, 3143, 3144,
    3145, 3146, 3147, 3148, 3149, 3150, 3151, 3152, 3153, 3154, 3155, 3156, 3157, 3158, 3159, 3160,
    3161, 3162, 3163, 3164, 3165, 3166, 3167, 3168, 3169, 3170, 3171, 3172, 3173, 3174, 3175, 3176,
    3177, 3178, 3179, 3180, 3181, 3182, 3183, 3184, 3185, 3186, 3187, 3188, 3189, 3190, 3191, 3192,
    3193, 3194, 3195, 3196, 3197, 3198, 3199, 3200, 3201, 3202, 3203, 3204, 3205, 3206, 3207, 3208,
    3209, 3210, 3211, 3212, 3213, 3214, 3215, 3216, 3217, 3218, 3219, 3220, 3221, 3222, 3223, 3224,
    3225, 3226, 3227, 3228, 3229, 3230, 3231, 3232, 3233, 3234, 3235, 3236, 3237, 3238, 3239, 3240,
    3241, 3242, 3243, 3244, 3245, 3246, 3247, 3248, 3249, 3250, 3251, 3252, 3253, 3254, 3255, 3256,
    3257, 3258, 3259, 3260, 3261, 3262, 3263, 3264, 3265, 3266, 3267, 3268, 3269, 3270, 3271, 3272,
    3273, 3274, 3275, 3276, 3277, 3278, 3279, 3280, 3281, 3282, 3283, 3284, 3285, 3286, 3287, 3288,
    3289, 3290, 3291, 3292, 3293, 3294, 3295, 3296, 3297, 3298, 3299, 3300, 3301, 3302, 3303, 3304,
    3305, 3306, 3307, 3308, 3309, 3310, 3311, 3312, 3313, 3314, 3315, 3316, 3317, 3318, 3319, 3320,
    3321, 3322, 3323, 3324, 3325, 3326, 3327, 3328, 3329, 3330, 3331, 3332, 3333, 3334, 3335, 3336,
    3337, 3338, 3339, 3340, 3341, 3342, 3343, 3344, 3345, 3346, 3347, 3348, 3349, 3350, 3351, 3352,
    3353,
)

internal fun getDecompositionByIndex(index: Int): IntArray {
    val startIndex = decompositionValueIndex[index].toInt()
    val endIndex = decompositionValueIndex[index + 1].toInt()
    val result = IntArray(endIndex - startIndex)
    decompositionValues.copyInto(result, startIndex = startIndex, endIndex = endIndex)
    return result
}